// https://www.lintcode.com/problem/k-th-symbol-in-grammar/my-submissions


class Solution {
public:
    /**
     * @param N: the row
     * @param K: the index
     * @return:  the K-th indexed symbol in row N
     */
    // MLE     
    // string solve(string num, int n)
    // {
    //     if (n <= 1)
    //         return num;
    //     int size = num.size();
    //     string newNum = "";
    //     for (int i = 0; i < size; ++i)
    //     {
    //         if (num[i] == '0')
    //             newNum += "01";
    //         else
    //             newNum += "10";
    //     }
    //     return solve(newNum, n - 1);
    // }
    // int kthGrammar(int N, int K) {
    //     string num = "0";
    //     string res = solve(num, N);
    //     // return atoi(res[K - 1]);
    //     return res[K - 1] - '0';
    // }
    
    // 满二叉树，看父节点（n-1层，(k+1)/2个）的值，然后看k奇偶，要不要补充^1
    int kthGrammar(int N, int K) {
        if (N == 0) return 0;
        return kthGrammar(N - 1, (K + 1) / 2) ^ (K & 1) ^ 1;
    }
    
    // 进行观察，对于每行第K个字符，如果K-1的二进制表示中有奇数个1时，返回1，如果有偶数个，返回0。
    // int kthGrammar(int N, int K) {
    //     // Write your code here
    //     int n;
    //     for (n = 0, K -= 1; K ; K &= (K - 1)){  //求解K-1的二进制中1的个数
    //         n++;
    //     }
    //     return n & 1;
    // }
};